
#include "BPlusTree.h"
#include <stdlib.h>
#include <iostream.h>
#include <limits.h>
#include <float.h>
Type whichType;

int Compare (const void *one, const void *two) {

	IndexRecord *recOne = (IndexRecord *) one;
	IndexRecord *recTwo = (IndexRecord *) two;

	return (recOne->Compare (*recTwo, whichType));
}

int BPlusTree :: Open (char *fName) {

	fileName = strdup (fName);
	char foo[200];
	sprintf (foo, "%s.header", fileName);
	FILE *myFile = fopen (foo, "r");

	fscanf (myFile, "keyType %s", foo);
	if (!strcmp (foo, "Int")) {
		keyType = Int;
		cout << "Got an Int\n";
	} else if (!strcmp (foo, "Double")) {
                keyType = Double;
		cout << "Got a Double\n";
	} else {
                keyType = String;
		cout << "Got a String\n";
	}

	fscanf (myFile, "%s %d", foo, &numPages);
	cout << "Are " << numPages << " pages.\n";
	fscanf (myFile, "%s %d", foo, &height);
	cout << "Are " << height << " levels.\n";
	fscanf (myFile, "%s %d", foo, &rootLocation);
	cout << "Root is at " << rootLocation << "\n";
	fclose (myFile);
	whereILive.Open (1, fName);
}

int BPlusTree :: Create (char *fName, Type keyyType) {

	// remember the key type
	keyType = keyyType;
	whichType = keyType;
	fileName = strdup (fName);

	// create the underlying file
	whereILive.Open (0, fName);

	// create the root, which points at location 1
	IndexRecord foo;
	char *max = GetMax ();
	Load (foo, max, 1);
	delete [] max;

	Page newRootPage;
	newRootPage.Append (foo);
	whereILive.AddPage (newRootPage, 0);
	rootLocation = 0;

	// create an empty leaf page
	Page leafPage;
	whereILive.AddPage (leafPage, 1);
	numPages = 2;

	// and the height is one
	height = 1;
	
}

void Sort (Page &sortMe) {
	
	// first, count all of the entries
	Page copy;
	IndexRecord temp;
	int counter = 0;
	while (sortMe.GetFirst (temp)) {
		counter++;
		copy.Append (temp);
	}

	// now, sort them
	IndexRecord *us = new IndexRecord[counter];
	for (int i = 0; i < counter; i++) {
		copy.GetFirst (us[i]);
	}
	qsort (us, counter, sizeof (Record), Compare);

	// and put them back into the page
	for (int i = 0; i < counter; i++) {
		temp.Consume (us[i]);
		sortMe.Append (temp);
	}
	delete [] us;
}

void BPlusTree :: Close () {
	char foo[200];
	sprintf (foo, "%s.header", fileName);
	FILE *myFile = fopen (foo, "w");

	if (keyType == Int) {
		fprintf (myFile, "keyType Int\n");
	} else if (keyType == Double) {
		fprintf (myFile, "keyType Double\n");
	} else {
		fprintf (myFile, "keyType String\n");
	}

	fprintf (myFile, "numPages %d\n", numPages);
	fprintf (myFile, "height %d\n", height);
	fprintf (myFile, "rootLocation %d\n", rootLocation);
	fclose (myFile);
	whereILive.Close ();
	delete stack;
	stack = 0;
}

int IndexRecord :: Compare (IndexRecord &withMe, Type myType) {
	
	if (myType == Int) {
		return *((int *) myData[0].data) - *((int *) withMe.myData[0].data);
	}
	if (myType == Double) {
		double res = *((double *) myData[0].data) - *((double *) withMe.myData[0].data);
		if (res < 0)
			return -1;
		else if (res > 0)
			return 1;
		else
			return 0;
	}
	return (strcmp (myData[0].data, withMe.myData[0].data));
}

int IndexRecord :: Compare (char *keyVal, Type myType) {

	if (myType == Int) {
		return *((int *) myData[0].data) - *((int *) keyVal);
	}
	if (myType == Double) {
		double res = *((double *) myData[0].data) - *((double *) keyVal);
		if (res < 0)
			return -1;
		else if (res > 0)
			return 1;
		else
			return 0;
	}
	return (strcmp (myData[0].data, keyVal));
}

IndexRecord :: IndexRecord () {

	delete [] myData;
	myData = new Att[2];
	mySize = sizeof (int) * 3;
	numAtts = 2;
}

char *IndexRecord :: GetKey () {

	char *space = new char[myData[0].len];
	memmove (space, myData[0].data, myData[0].len);
	return space;
}

int IndexRecord :: GetPointer () {
	return myData[1].GetInt ();
}

BPlusTree :: BPlusTree () {
	stack = 0;
}

BPlusTree :: ~BPlusTree () {}

void BPlusTree :: Insert (char *keyVal, int pageID) {

	// note that we have not traversed
	delete [] stack;
	stack = 0;

	// first, get the root node
	Page root;
	whereILive.GetPage (root, rootLocation);

	// and insert it
	char *splitKey;
	int newAddress = Insert (keyVal, pageID, root, rootLocation, height, splitKey);

	// if we got a root split, then deal with it
	if (newAddress != -1) {
	
		// if the recursive insert DID result in a split, deal with it
		// first, we create the new index records
		IndexRecord newIndexRec1;
		Load (newIndexRec1, splitKey, rootLocation);
		delete [] splitKey;

		IndexRecord newIndexRec2;
		char *max = GetMax ();
		Load (newIndexRec2, max, newAddress);
		delete [] max;

		// now create a new root page
		Page newRootPage;
		newRootPage.Append (newIndexRec1);
		newRootPage.Append (newIndexRec2);
		whereILive.AddPage (newRootPage, numPages);
		rootLocation = numPages;
		numPages++;
		height++;
	}
}

char *BPlusTree :: GetMax () {

	char *max = new char[10];
	if (keyType == Int)
		*((int *) max) = INT_MAX;
	else if (keyType == Double)
		*((double *) max) = DBL_MAX;
	else strcpy (max, "ZZZZZZ");
	
	return max;
}

// load a key into a B+-Tree record
void BPlusTree :: Load (IndexRecord &foo, char *keyVal, int pageID) {

	if (keyType == Int) {
		foo.SetInt (*((int *) keyVal), 0);
	} else if (keyType == Double) {
		foo.SetDouble (*((double *) keyVal), 0);
	} else {
		foo.SetString (keyVal, 0);
	}
	foo.SetInt (pageID, 1);

}




// this "adds" foo to curPage, then sorts and splits the result.  curPage is re-written at address
// pageAddress, and the upper half is written at the end of the file.  splitKey is the value of the
// largest key present in curPage after the split, and the return value is the location where the
// new page was written
int BPlusTree :: Split (Page &curPage, int pageAddress, IndexRecord &foo, char *&splitKey) {

	// first, count all of the entries
	Page copy;
	IndexRecord temp;
	int counter = 0;
	while (curPage.GetFirst (temp)) {
		counter++;
		copy.Append (temp);
	}

	// now, sort them
	IndexRecord *us = new IndexRecord[counter + 1];
	for (int i = 0; i < counter; i++) {
		copy.GetFirst (us[i]);
	}
	us[counter].Consume (foo);
	counter++;
	qsort (us, counter, sizeof (Record), Compare);

	// and put them into the two new pages; the "low" page is first
	for (int i = 0; i < counter / 2; i++) {
		temp.Consume (us[i]);

		// see if this is the splitting record
		if (i == counter / 2 - 1) {
			splitKey = temp.GetKey ();
		}
		curPage.Append (temp);
	}
		
	// and the "high" page is second
	for (int i = counter / 2; i < counter; i++) {
		temp.Consume (us[i]);
		copy.Append (temp);
	}

	// now, write out the low page
	whereILive.AddPage (curPage, pageAddress);

	// and write out the high page
	whereILive.AddPage (copy, numPages);
	numPages++;

	delete [] us;

	// done!!!
	return numPages - 1;
	
}

IndexRecord *BPlusTree :: GetNext (int &numReturned) {

	if (stack == 0) {
		cerr << "Can't call GetNext w/o calling GetPage first!!!\n";
		exit (1);
	}
		
	Page root;
	whereILive.GetPage (root, rootLocation);
	return GetNext (root, height, numReturned);
}

IndexRecord *BPlusTree :: GetNext (Page &curPage, int height2Go, int &numReturned) {

	if (height2Go == 0) {

		IndexRecord foo;
		Page tempPage;
		numReturned = 0;
		while (curPage.GetFirst (foo)) {
			numReturned++;
			tempPage.Append (foo);
		}

		IndexRecord *allRecs = new IndexRecord[numReturned];
		for (int i = 0; i < numReturned; i++) {
			tempPage.GetFirst (allRecs[i]);
		}
		return allRecs;
	} else {

		IndexRecord foo;
		while (curPage.GetFirst (foo)) {
		
			// see if we found the one we got last time
			if (foo.GetPointer () == stack[height - height2Go] || stack[height - height2Go] == -1) {
				
				Page root;
				IndexRecord *result = 0;

				// if the next record level is not a leaf, then go down there
				if (height2Go != 1 || stack[height - height2Go] == -1) {
					whereILive.GetPage (root, foo.GetPointer ());
					stack[height - height2Go] = foo.GetPointer ();
					result = GetNext (root, height2Go - 1, numReturned);
				}

				// see if this path was not successful, or if the next level was a leaf
				if (result == 0) {

					// try to go to the next tree
					if (curPage.GetFirst (foo)) {

						stack[height - height2Go] = foo.GetPointer ();
						for (int i = height - height2Go + 1; i < height; i++) {
							stack[i] = -1;
						}
						whereILive.GetPage (root, foo.GetPointer ());
						result = GetNext (root, height2Go - 1, numReturned);
					}

				}

				return result;
			}
		}	

	}
}

IndexRecord *BPlusTree :: GetPage (char *keyVal, int &numReturned) {

	delete [] stack;
	stack = new int[height];
	Page root;
	whereILive.GetPage (root, rootLocation);
	return GetPage (root, height, keyVal, numReturned);
}

IndexRecord *BPlusTree :: GetPage (Page &curPage, int height2Go, char *keyVal, int &numReturned) {

	if (height2Go == 0) {

		IndexRecord foo;
		Page tempPage;
		numReturned = 0;
		while (curPage.GetFirst (foo)) {
			numReturned++;
			tempPage.Append (foo);
		}

		IndexRecord *allRecs = new IndexRecord[numReturned];
		for (int i = 0; i < numReturned; i++) {
			tempPage.GetFirst (allRecs[i]);
		}
		return allRecs;
	} else {

		IndexRecord foo;
		while (curPage.GetFirst (foo)) {
		
			// in this case, we found the correct entry
			if (foo.Compare (keyVal, keyType) >= 0) {

				stack[height - height2Go] = foo.GetPointer ();

				// load up the page corresponding to the child
				Page root;
				whereILive.GetPage (root, foo.GetPointer ());
				return GetPage (root, height2Go - 1, keyVal, numReturned);
			}
		}	

	}
}

int BPlusTree :: Insert (char *keyVal, int pageID, Page &curPage, int pageAddress, int heightToGo, char *&splitKey) {

	// base case
	if (heightToGo == 0) {

		// just insert it
		IndexRecord foo;
		Load (foo, keyVal, pageID);
		if (curPage.Append (foo)) {
			Sort (curPage);
			whereILive.AddPage (curPage, pageAddress);
			return -1;
		}

		// we could not insert it, so split the page in two
		return Split (curPage, pageAddress, foo, splitKey);
	}

	// if we got here, we have a kid, so do a recursive insert
	IndexRecord foo;

	while (curPage.GetFirst (foo)) {
		
		// in this case, we found the correct entry
		if (foo.Compare (keyVal, keyType) >= 0) {

			// load up the page corresponding to the child
			Page root;
			whereILive.GetPage (root, foo.GetPointer ());
				
			// recursively insert
			char *childSplitKey;
			int newAddress = Insert 
				(keyVal, pageID, root,  foo.GetPointer (), heightToGo - 1, childSplitKey);

			// see if this recursive insert did not result in a split
			if (newAddress == -1) {
				return -1;
			}

			// if the recursive insert DID result in a split, deal with it
			// first, we create the new index records
			IndexRecord newIndexRec1;
			Load (newIndexRec1, childSplitKey, foo.GetPointer ());
			delete [] childSplitKey;

			IndexRecord newIndexRec2;
			char *tempKey = foo.GetKey ();
			Load (newIndexRec2, tempKey, newAddress);
			delete [] tempKey;

			// re-load the current index record into the page
			curPage.Append (newIndexRec2);

			// now try to load the new index record
			if (curPage.Append (newIndexRec1)) {
				Sort (curPage);
				whereILive.AddPage (curPage, pageAddress);
				return -1;
			}

			// if we got here, there was not enough space to add the new record
			return Split (curPage, pageAddress, newIndexRec1, splitKey);
		}

		// put the reocrd that we took out back in
		curPage.Append (foo);
	}
}
